#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

namespace lh
{

    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) : val(x), next(nullptr) {}
    };

	//BM13 判断一个链表是否为回文结构
	//https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f?tpId=295&tqId=1008769&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution {
    public:
        /**
         *
         * @param head ListNode类 the head
         * @return bool布尔型
         */
        bool isPail(ListNode* head) {
            // write code here
            //链表不能随意访问，但是数组可以
            vector<int>nums;
            while (head)
            {
                nums.push_back(head->val);
                head = head->next;
            }
            //确定双指针位置
            int left = 0;
            int right = nums.size() - 1;
            while (left < right)
            {
                if (nums[left] != nums[right])
                {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }
    };
    void test()
    {
        ListNode* node1 = new ListNode(1);
        ListNode* node2 = new ListNode(2);
        ListNode* node3 = new ListNode(2);
        ListNode* node4 = new ListNode(1);

        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        cout << Solution().isPail(node1) << endl;

        delete node1;
        delete node2;
        delete node3;
        delete node4;

    }
    //BM14 链表的奇偶重排
    //https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3?tpId=295&tqId=1073463&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution2 {
    public:
        ListNode* oddEvenList(ListNode* head) {
            // 双指针，一个指向奇数位开头，一个指向偶数位开头，每次移动2个指针。将一个链表断开为2个链表
            //奇数位连接偶数位后一个节点，偶数位连接奇数位后一个节点
            if (head == nullptr)
                return nullptr;
            //奇数位odd
            ListNode* odd = head;
            //偶数位even,可能为空
            ListNode* even = head->next;
            //记录偶数位头，用来给奇数位尾连接
            ListNode* even_head = even;
            //每次遍历even在后面，所以只需要判断even和even->next是否为空来做边界
            while (even && even->next)
            {
                //连接
                odd->next = even->next;
                //更新移动到新节点
                odd = odd->next;

                even->next = odd->next;
                even = even->next;
            }
            //奇数位链表连接偶数位链表
            odd->next = even_head;
            return head;

        }
    };
    void test2()
    {
        ListNode* node1 = new ListNode(1);
        ListNode* node2 = new ListNode(4);
        ListNode* node3 = new ListNode(6);
        ListNode* node4 = new ListNode(3);
        ListNode* node5 = new ListNode(7);

        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
        ListNode* res=Solution2().oddEvenList(node1);

        while (res)
        {
            cout << res->val << "->";
            res = res->next;
        }
        cout << endl;

        delete node1;
        delete node2;
        delete node3;
        delete node4;
        delete node5;
        delete res;
    }
    //BM15 删除有序链表中重复的元素-I
    //https://www.nowcoder.com/practice/c087914fae584da886a0091e877f2c79?tpId=295&tqId=664&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution3 {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            // write code here
            //双指针:不相等，前指针指向后指针，再同时移动指针到next，若相等则只移动后指针
            if (head == nullptr)
                return nullptr;
            ListNode* slow = head;
            ListNode* fast = head->next;
            while (fast)
            {
                if (fast->val != slow->val)
                {
                    slow->next = fast;
                    slow = slow->next;
                }
                fast = fast->next;
            }
            //最后手动把末尾置空节点,为了将最后一段的重复节点清除
            slow->next = fast;
            return head;
        }
    };
    void test3()
    {
        ListNode* node1 = new ListNode(1);
        ListNode* node2 = new ListNode(2);
        ListNode* node3 = new ListNode(2);
        ListNode* node4 = new ListNode(3);

        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        ListNode* res = Solution3().deleteDuplicates(node1);

        while (res)
        {
            cout << res->val << "->";
            res = res->next;
        }
        cout << endl;

        delete node1;
        delete node2;
        delete node3;
        delete node4;
        delete res;
    }
    //BM16 删除有序链表中重复的元素-II
    //https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId=295&tqId=663&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution4 {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            // 遍历链表，一次性跳过出现的相同值，指向只出现一次的节点
            //建立表头
            ListNode* res = new ListNode(-1);
            res->next = head;

            //cur表示当前轮所在开始遍历位置
            ListNode* cur = res;
            //一次判断两个节点
            while (cur->next && cur->next->next)
            {
                //遇到相邻节点值相同
                if (cur->next->val == cur->next->next->val)
                {
                    //找到相同的值
                    int tmp = cur->next->val;
                    //跳过相同的值
                    while (cur->next && cur->next->val == tmp)
                    {   //断开指向新后继，继续判断新后继是否是重复的值
                        cur->next = cur->next->next;
                    }
                }
                //不相同则后移，从后一个节点开始新一轮
                else
                {
                    cur = cur->next;
                }
            }
            return res->next;

        }
    };
    void test4()
    {
        ListNode* node1 = new ListNode(1);
        ListNode* node2 = new ListNode(2);
        ListNode* node3 = new ListNode(3);
        ListNode* node4 = new ListNode(3);
        ListNode* node5 = new ListNode(4);
        ListNode* node6 = new ListNode(4);
        ListNode* node7 = new ListNode(5);

        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
        node5->next = node6;
        node6->next = node7;
        ListNode* res = Solution4().deleteDuplicates(node1);

        while (res)
        {
            cout << res->val << "->";
            res = res->next;
        }
        cout << endl;

        delete node1;
        delete node2;
        delete node3;
        delete node4;
        delete node5;
        delete node6;
        delete node7;
        delete res;
    }
};

int main()
{
    cout << "BM13:判断一个链表是否为回文结构" << endl;
    lh::test();
    cout << "BM14:链表的奇偶重排" << endl;
    lh::test2();
    cout << "BM15:删除有序链表中重复的元素-I" << endl;
    lh::test3();
    cout << "BM16:删除有序链表中重复的元素-II" << endl;
    lh::test4();
    return 0;
}